package 剑指offer.第9天;

/**
 * 剑指 Offer 42. 连续子数组的最大和
 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 要求时间复杂度为O(n)。
 示例1:
 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 输出: 6
 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 */
class Solution {
    public int maxSubArray1(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for(int i=1;i < nums.length;i++){
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
            max = Math.max(max,dp[i]);
        }
        return max;
    }

    /**把这个常规动态规划的代码 化简一下就变成了下面那个代码，这个常规dp应该好理解
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        int n = nums.length;
        // dp[i]表示以nums[i]结尾的子数组的和的最大值
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < n; i++) {
            if (dp[i - 1] > 0) dp[i] = dp[i - 1] + nums[i];
            else dp[i] = nums[i];
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    /**learned 思想：前面的数累加的和如果小于0，则直接从当前值重新开始累加
     * @param nums
     * @return
     */
    public int maxSubArray3(int[] nums) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (sum <= 0) {
                sum = num;
            } else {
                sum += num;
            }
            max = Math.max(max, sum);
        }
        return max;
    }

    /**learned 逻辑判断麻烦呀 直接用函数好理解一些。
     * @param nums
     * @return
     */
    public int maxSubArray4(int[] nums) {
        int sum = 0;
        int max = nums[0];
        for(int num: nums) {
            sum = Math.max(sum+num,num);
            max = Math.max(sum, max);
        }
        return max;
    }

    /**
     * learned 思想：前面的数累加的和如果小于0，则直接从当前值重新开始累加
     * @param nums
     * @return
     */
    public int maxSubArray5(int[] nums) {
        int max_sum=nums[0];   //最大和
        int cur_sum=0;  //当前的和
        for(int i=0;i<nums.length;i++){
            //如果前面序列的和小于0，那么从当前数重新开始累加
            if(cur_sum<=0) {
                cur_sum=nums[i];
            }
            else {
                cur_sum=cur_sum+nums[i];
            }
            if(cur_sum>max_sum) {
                max_sum = cur_sum;
            }
        }
        return max_sum;
    }

    /**learned
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int preSum = 0, res = Integer.MIN_VALUE;
        for (int num : nums) {
            preSum = preSum < 0 ? num : preSum + num;
            res = Math.max(res, preSum);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int i = new Solution().maxSubArray(nums);
        System.out.println("i = " + i);
    }
}